/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package csm.uttils;

import csm.uttils.generics.Roster;

/**
 *
 * @author Gaston Quiroga
 */
public class QuickSort extends Order
{
    /**
     * Orders the entered array, recursively
     * with the method quicksort
     * @param ar arreglo a ordenar
     * @param izq
     * @param der
     * @return
     */
    private static Comparable[] sortQ(Comparable[] ar,int izq, int der)
    {
       Comparable x,y;
       int i, j;
       i = izq;
       j = der;
       x = ar[(izq + der) / 2];
       do
       {
            while (ar[i].compareTo(x) < 0 && i < der) i++;
            while (x.compareTo(ar[j]) < 0 && j > izq ) j--;
            if (i  <=  j)
            {
                  y = ar[i];
                  ar[i] = ar[j];
                  ar[j] = y;
                  i++;
                  j--;
            }
       }
       while (i  <=  j );
       if ( izq  <  j ) ar=sortQ(ar,izq, j);
       if ( i  < der ) ar=sortQ(ar,i, der);
       return ar;
    }//fin ordenarQ

    /**
     * Llama al metodo ordenar, haciendo q este ordene el arreglo
     * entrado por parametros, con el metodo quicksort y luego lo devuelve.
     * @param ar
     * @return
     */
    @Override
    public Comparable[] sortArray(Comparable[] ar)
    {
       return sortQ(ar, 0, ar.length-1);
    }//Fin sortArray

    /**
     * Devuelve una lista ordenada con el algoritmo QuickSort
     * en base a una lista ingresada por aprametro
     * @param ls
     * @return
     */
    @Override
    public Roster sortRoster(Roster ls)
    {
       Comparable[] ar= ls.toArray();
       return Convertion.toRoster(sortArray(ar));
    }//fin sortRoster


}
